package array;

/**
 * 给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。
 * 从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。
 * <p>
 * 示例 1：
 * 输入：nums = [0,2,1,5,3,4]
 * 输出：[0,1,2,4,5,3]
 * 解释：数组 ans 构建如下：
 * ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
 * = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
 * = [0,1,2,4,5,3]
 * <p>
 * 示例 2：
 * 输入：nums = [5,0,1,2,3,4]
 * 输出：[4,5,0,1,2,3]
 * 解释：数组 ans 构建如下：
 * ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
 * = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
 * = [4,5,0,1,2,3]
 *
 * @author Jisheng Huang
 * @version 20250506
 */
public class BuildArrFromPermutation_1920_2 {
    /**
     * 我们也可以直接对原数组 nums 进行修改。
     * 为了使得构建过程可以完整进行，我们需要让 nums 中的每个元素 nums[i] 能够同时存储「当前值」（即 nums[i]）和「最终值」
     * （即 nums[nums[i]]）。
     * 我们注意到 nums 中元素的取值范围为 [0,999] 闭区间，这意味着 nums 中的每个元素的「当前值」和「最终值」都在 [0,999] 闭区间内。
     * 因此，我们可以使用类似「1000 进制」的思路来表示每个元素的「当前值」和「最终值」。对于每个元素，我们用它除以 1000 的商数表示它的
     * 「最终值」，而用余数表示它的「当前值」。
     * 那么，我们首先遍历 nums，计算每个元素的「最终值」，并乘以 1000 加在该元素上。随后，我们再次遍历数组，并将每个元素的值除以 1000
     * 保留其商数。此时 nums 即为构建完成的数组，我们返回该数组作为答案。
     * <p>
     * 细节
     * 在计算 nums[i] 的「最终值」并修改该元素时，我们需要计算修改前 nums[nums[i]] 的值，而 nums 中下标为 nums[i] 的元素可能已被修改，因此我们需要将取下标得到的值对 1000 取模得到「最终值」。
     *
     * @param nums the given array
     * @return the array after the transformation
     */
    public static int[] buildArray(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; ++i) {
            nums[i] += n * (nums[nums[i]] % n);
        }

        for (int i = 0; i < n; ++i) {
            nums[i] /= n;
        }

        return nums;
    }

    public static void main(String[] args) {
        int[] nums = {0, 2, 1, 5, 3, 4};
        int[] ans = buildArray(nums);

        for (int i : ans) {
            System.out.print(i + " ");
        }

        System.out.println();

        nums = new int[]{5, 0, 1, 2, 3, 4};
        ans = buildArray(nums);

        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}
